/*    Copyright 2010 Tobias Marschall
 *
 *    This file is part of MoSDi.
 *
 *    MoSDi is free software: you can redistribute it and/or modify
 *    it under the terms of the GNU General Public License as published by
 *    the Free Software Foundation, either version 3 of the License, or
 *    (at your option) any later version.
 *
 *    MoSDi is distributed in the hope that it will be useful,
 *    but WITHOUT ANY WARRANTY; without even the implied warranty of
 *    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *    GNU General Public License for more details.
 *
 *    You should have received a copy of the GNU General Public License
 *    along with MoSDi.  If not, see <http://www.gnu.org/licenses/>.
 */

package mosdi.util.iterators;

import java.util.LinkedList;
import java.util.Iterator;
import java.util.NoSuchElementException;
import java.util.HashSet;

import mosdi.util.TreeNode;

public class LevelWiseIterator<T extends TreeNode> implements Iterator<T> {
	private LinkedList<T> lastLevelsNodes;
	private LinkedList<T> currentLevelsNodes;
	// TODO: cleanup! this is only necessary because our trees are not actually trees 
	private HashSet<T> levelSet;
	private Iterator<T> lastLevelIterator;
	private Iterator<? extends TreeNode> childrenIterator;
	private int currentDepth;
	private T nextNode;
	private int minDepth;
	private int maxDepth;
	private int nextDepth;
	private int lastDepth;
	
	public LevelWiseIterator(T node) {
		minDepth=-1;
		maxDepth=-1;
		init(node);
	}

	public LevelWiseIterator(T node, int minDepth, int maxDepth) {
		this.minDepth=minDepth;
		this.maxDepth=maxDepth;
		init(node);
	}
	
	private void init(T node) {
		currentDepth=1;
		lastDepth=-1;
		lastLevelsNodes = new LinkedList<T>();
		currentLevelsNodes = new LinkedList<T>();
		levelSet = new HashSet<T>();
		lastLevelsNodes.add(node);
		lastLevelIterator=new EmptyIterator<T>();
		childrenIterator=node.children(); 
		nextNode=node;
		nextDepth=0;
		if (minDepth>0) step();
	}
	
	private void step() {
		if (nextNode==null) return;
		while (true) {
			while (!childrenIterator.hasNext()) {
				if (!lastLevelIterator.hasNext()) {
					lastLevelsNodes = currentLevelsNodes;
					currentLevelsNodes = new LinkedList<T>();
					levelSet.clear();
					lastLevelIterator = lastLevelsNodes.iterator();
					++currentDepth;
					if ((maxDepth>=0) && (currentDepth>maxDepth)) {
						nextNode=null;
						return;
					}
				}
				if (!lastLevelIterator.hasNext()) {
					nextNode=null;
					return;
				}
				childrenIterator=lastLevelIterator.next().children();
			}
			nextDepth=currentDepth;
			nextNode=(T)childrenIterator.next();
			if (!levelSet.add(nextNode)) continue;
			currentLevelsNodes.add(nextNode);
			if ((minDepth==-1) || (nextDepth>=minDepth)) break;
		}
	}

	/** Returns the depth of node last returned by next(). */
	public int getDepth() {
		return lastDepth;
	}
	
	public boolean hasNext() {
		return nextNode!=null;
	}

	public T next() {
		if (nextNode!=null) {
			lastDepth = nextDepth;
			T result = nextNode;
			step();
			return result;
		}
		else throw new NoSuchElementException();
	}

	public void remove() { throw new UnsupportedOperationException(); }
}
